The prior art will now be described with reference to the following drawings in which:
FIG. 1 is a view of a conventional single pixel of a CRT type display;
FIG. 2 is a representation of a unit colour cube; and
FIG. 3 is a diagrammatic representation of the Floyd and Steinberg error diffusion process.
Colour raster graphic display devices are well known in the art. The display of colour images in these devices is normally achieved by means of a pixel map. A pixel map normally consists of individual pixels. Each pixel in turn consists of a collection of bits which represent the colour value of that pixel on the display device. The number of different possible bits in this collection is related to the number of different colours which may be displayed by the display device and hence the resolution with which the device can display a given picture. Common colour systems store 8 or 24 bits per pixel, although other variations are possible.
A display device displays the corresponding colour value of the pixel, often to a high resolution. Common screen displays are capable of displaying a number of different pixels in the range of 1280 by 1024 pixels with each pixel capable of displaying up to 2.sup.24 different colour values.
Colours are often displayed on a computer display according to a particular model. The red, green, blue (RGB) colour model is one that is in common use with Cathode Ray Tubes (CRT) and colour raster display devices. Other colour display models include cyan, magenta, yellow (CMY) often used in colour-printing devices. One example of an RGB model is in the NTSC picture display standard in cogon use with computer displays. In this standard, each pixel element is divided into 3 separate sub groupings. These separate subgroupings represent the Red, Green and Blue portion of a given pixel element respectively.
Referring now to FIG. 1, the viewing surface of a colour CRT often consists of closely spaced, pixels 1. Each pixel is made up of a red (R), green(G) and blue (B) phosphor dot or pixel element. These dots are so small that light emanating from the individual dots is perceived by the viewer as a mixture of the corresponding three colours. A wide range of different colours can thus be produced by a given pixel by variation of the strength with which each phosphor dot is excited. A conversion arrangement (not shown) is normally provided so that the strength of each phosphor dot's excitation has some proportionality to the value of each of the above mentioned pixel element subgrouping. By way of example, a 24 bits per pixel colour display system can be divided into 8 bits for each of the three colours red, green and blue. This corresponds to 2.sup.8 or 256 separate intensity levels of each of red, green and blue respectively and 2.sup.24 different colour values. A colour display capable of displaying this many colours can approximate a continuous tone image to such a degree that for all practical purposes the display can be considered to be a continuous tone display.
In order to conceptualize the range of colours that can be printed by this method it is helpful to map these colours into a unit cube as shown in FIG. 2. The individual contributions of each of the 3 separate subgroups at any one particular point are added together to yield the final colour. For example, the main diagonal of the cube, with equal amounts of each primary, represents the different grey levels or grey scale, from black (0,0,0) to white (1,1,1)
Many display devices are unable to actually display the full range of colours provided by, for example, a 24 bit input pixel. For example, a black and white raster image display can only display two colours, namely black and white and is known as a bi-level device. Other colour display devices can only display a finite number of discrete intensity levels for each primary colour. By way of further example, in a colour bi-level device, such as a bi-level ferroelectric liquid crystal display (FLCD), each pixel element on the screen can be at just two intensity levels, either fully on or fully off. If, for example, a display device can display red, green, blue and white primary colours the total number of different colours that each pixel can display will be 2.sup.4 =16 different colours.
If the input to the display device assumes that there is a larger number of intensity levels then there will be an error in the colour displayed, being the difference between the exact pixel value required to be displayed and the approximated value actually displayed. Methods have been developed to increase the number of colours displayable on an discrete colour display device such as a bi-level colour display. The methods used are known generally as halftoning. For an explanation of the different aspects of halftoning, reference is made to `Digital Halftoning` by Robert Ulichney, published in 1991 by MIT Press.
One method described by Ulichney to improve the quality of a displayed image is called error diffusion. This process was developed by Floyd and Steinberg for a single colour (black or white) display and is described in "An Adaptive Algorithm for Spatial Gray Scale", Society for Information Display 1975 Symposium Digest of Technical Papers, 1975, 36. In the Floyd and Steinberg algorithm, the error associated with each pixel value is added to the values of some of the neighbouring pixels of the given current pixel in such a manner that the sum of these additions is equal to the error associated with the pixel value. This has the effect of spreading or diffusing the error over several pixels in the final image to give an improved quality image. An example of this process is shown in FIG. 3. In this example a decision is made to spread the error associated with a current pixel 3, such that two eighths of the error is assigned to a pixel 4 on the right of the current pixel 3, one-eighths is assigned to its neighbour 5, two eighths is assigned to a pixel 6 below the current pixel 3, one eighths is assigned to pixels marked 7, 8, 9 respectively.
One method known of extending the error diffusion process to three dimensions so as to be to be applicable to colour displays is that set out in `Color Image Quantization for Frame Buffer Display` by Paul Heckbert, published in Computer Graphics, Volume 16, Number 3, July 1982, pages 297-304 and is also disclosed in an IBM Technical Disclosure Bulletin Vol. 29, No3, August 1986, Pages 1329 to 1334.
In the Heckbert process, the different possible output values of the display are chosen as the representative colours of the colour gamut of displayable images. A vector measure in a 3-dimensional colour space representing the distance between the nearest displayable colour value and a current input colour value is computed and this value is then preferably added to neighbouring pixels using the Floyd and Steinberg process.
High resolution displays in use commonly have pixel resolutions in the order of 1,280.times.1,024=1,310,720 pixels and a refresh rate in the order of 60 Hz. As mentioned previously, each pixel can have 24 bits associated with its colour value.
It therefore follows that, if any processing of the pixels must be undertaken, then the high input rate of pixels would require this processing to be performed at high speeds.
In the above example, a total capacity of over 235 mega bytes per second would have to be handled by a system wishing to process the display input data. Error diffusion is an example of process which requires high processing rates, as each pixel must be looked at and the errors diffused to neighbouring pixels. Additionally, the error diffusion process is difficult to implement in any other than a serial manner as the error diffusion of one pixel element will influence all subsequent elements that are to be processed.
By the choice of neighbouring pixels that are below or to the right of a current pixel, the error diffusion can be achieved by one top-to-bottom pass over the image, as the errors diffused from a current pixel can then only influence subsequent pixels.
It is an object of the present invention to provide a method and apparatus for error diffusion of images at a high pixel rate through the use of parallelism.